import java.util.*;

class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}
class TreeNode {
    int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
}
class Solution {
    //N叉树的层序遍历
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new ArrayList<>();
        Node cur = root;
        Queue<Node> queue = new LinkedList<>();
        //先将根节点放入队列中
        if(cur == null) return ret;
        int count = 0;
        queue.add(cur);
        while (!queue.isEmpty()){
            //先记录队列元素
            count = queue.size();
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < count; i++) {
                cur = queue.poll();//将队头元素出队
                tmp.add(cur.val);
                for (Node child: cur.children) {//将队头元素的孩子节点放入队列中
                    queue.add(child);
                }
            }
            ret.add(tmp);
        }
        return ret;
    }
    //二叉树的锯齿形层序遍历
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        int flag = 1;
        TreeNode cur = root;
        //先将根节点放入队列中
        if(cur == null) return ret;
        queue.add(cur);
        int count = 0;
        while(!queue.isEmpty()){
            //先记录当前队列元素个数
            count = queue.size();
            //依次出队列
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < count; i++){
                cur = queue.poll();
                list.add(cur.val);
                //将其孩子节点入队列
                if(cur.left != null) queue.add(cur.left);
                if(cur.right != null) queue.add(cur.right);
            }
            //判断是否需要逆序
            if(flag == -1){
                List<Integer> tmp = new ArrayList<>();
                for (int i = list.size() - 1; i >= 0; i--) {
                    tmp.add(list.remove(i));
                }
                ret.add(tmp);
            }else{
                ret.add(list);
            }
            flag = -flag;

        }
        return ret;
    }
    //在每个树行中找最大值
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        TreeNode cur = root;
        Queue<TreeNode> queue = new LinkedList<>();
        //先将根节点放入
        if(cur == null) return ret;
        queue.add(cur);
        int count = 0;
        while(!queue.isEmpty()){
            //先计算队列中有多少个元素
            count = queue.size();
            //将元素依次出队列
            int max = Integer.MIN_VALUE;
            for(int i = 0; i < count; i++){
                cur = queue.poll();
                if(max < cur.val){
                    max = cur.val;
                }
                //将其孩子节点放入队列中
                if(cur.left != null) queue.add(cur.left);
                if(cur.right != null) queue.add(cur.right);
            }
            ret.add(max);
        }
        return ret;
    }

    //二叉树的最大宽度
//    public int widthOfBinaryTree(TreeNode root) {
//        TreeNode cur = root;
//        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
//        queue.add(new Pair<TreeNode, Integer>(root, 1));
//        int count = 0;
//        int ret = 1;
//        while(!queue.isEmpty()){
//            count = queue.size();
//            int left = 0, right = 0;
//            for(int i = 0; i < count; i++){
//                Pair<TreeNode, Integer> pair = queue.poll();
//                int index = pair.getValue();
//                if(i == 0) left = index;
//                if(i == count - 1) right = index;
//                cur = pair.getKey();
//                if(cur.left != null) queue.add(new Pair<TreeNode, Integer>(cur.left, index*2));
//                if(cur.right != null) queue.add(new Pair<TreeNode, Integer>(cur.right, index*2 + 1));
//            }
//            ret = Math.max(ret, right - left + 1);
//        }
//        return ret;
//    }
    //微信红包
    public int getValue(int[] gifts, int n) {
        // write code her
        Map<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < gifts.length; i++){
            hash.put(gifts[i], hash.getOrDefault(gifts[i], 0) + 1);
        }
        //遍历哈希表
        Iterator<Map.Entry<Integer, Integer>> iterator = hash.entrySet().iterator();
        int ret = 0;
        while(iterator.hasNext()){
            Map.Entry<Integer, Integer> entry = iterator.next();
            if(entry.getValue() > n/2){
                ret = entry.getKey();
                break;
            }
        }
        return ret;
    }
}